impl Solution {
    pub fn num_triplets(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> i32 {
        nums1.sort();
        nums2.sort();
        return Solution::f_num_triplets(&nums1, &nums2) + Solution::f_num_triplets(&nums2, &nums1);
    }
    fn f_num_triplets(nums1: &[i32], nums2: &[i32]) -> i32 {
        let l2 = nums2.len();
        let mut ans = 0;
        let mut last_ind = 0;
        for &val in nums1.iter() {
            let val_sqr = (val as i64).pow(2);
            for ind in last_ind..l2 {
                if nums2[ind] as i64 * (nums2[l2 - 1] as i64) < val_sqr {
                    last_ind += 1;
                } else {
                    break;
                }
            }
            for j in last_ind..l2 {
                if val_sqr % (nums2[j] as i64) != 0 {
                    continue;
                }
                ans+=Solution::bs(&nums2[j + 1..l2], (val_sqr / (nums2[j] as i64)) as i32);
            }
        }
        return ans;
    }
    fn bs(nums: &[i32], target: i32) -> i32 {
        if nums.len()==0{
            return 0;
        }
        let mut ans =0;
        let mut l = 0;
        let mut r = nums.len();
        let mut j :Option<usize>=None;
        while l < r {
            let mid = l + (r - l) / 2;
            if nums[mid] == target {
                j=Some(mid);
                break;
            } else if nums[mid] < target {
                l=mid+1;
            } else {
                r = mid;
            }
        }
        if let Some(j)=j{
            ans=1;
            for i in (0..j).rev(){
                if nums[i]==target{
                    ans+=1;
                }else{
                    break;
                }
            }
            for i in j+1..nums.len(){
                if nums[i]==target{
                    ans+=1;
                }else{
                    break
                }
            }
        }
        return ans;
    }
}
